package com.waiting.leetcode;

import java.util.List;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/13
 **/
public class SumRootToLeafNumbers129 {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(4);
        TreeNode b = new TreeNode(9);
        TreeNode c = new TreeNode(0);
        TreeNode d = new TreeNode(5);
        TreeNode e = new TreeNode(1);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        SumRootToLeafNumbers129 testOb = new SumRootToLeafNumbers129();
        System.out.println(testOb.sumNumbers(a));
    }

    public int sumNumbers(TreeNode root) {
//        List<Integer> test = new LinkedList<>();
//        ite(root, test);
//        return sum;
        ite(root, 0);
        return sum;
    }

    private int sum = 0;

    public void ite(TreeNode root, List<Integer> path) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            int sumTmp = 0;
            for (int i = 0; i < path.size(); i++) {
                sumTmp = sumTmp * 10 + path.get(i);
            }
            sumTmp = sumTmp * 10 + root.val;
            sum += sumTmp;
            return;
        }
        int size = path.size();
        path.add(Integer.valueOf(root.val));
        ite(root.left, path);
        ite(root.right, path);
        path.remove(size);
    }

    public void ite(TreeNode root, int sumTmp) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            sum += sumTmp * 10 + root.val;
        } else {
            sumTmp = sumTmp * 10 + root.val;
            ite(root.left, sumTmp);
            ite(root.right, sumTmp);
        }
    }
}
